/**
 * 旋转链表
 *
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * 示例 1：
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 *
 * 示例 2：
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 *
 * 提示：
 * 链表中节点的数目在范围 [0, 500] 内
 * -100 <= Node.val <= 100
 * 0 <= k <= 2 * 109
 */

/**
 * 咱观察我们需要反转的节点实际上就是一个整体的头插, 不看过程, 那么咱只需要将
 * 需要整体头插的第一个节点和最后一个节点求出来就可以了, 当然别忘记了头插完后
 * 的最后一个节点的 next 需要置为 null
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public ListNode rotateRight(ListNode head, int k) {

        // 创建虚拟节点
        ListNode newHead = new ListNode(0);
        newHead.next = head;

        // 链表的长度
        int n = 0;

        // 打工节点
        ListNode cur = newHead;

        while (cur.next != null) {
            n++;
            cur = cur.next;
        }

        // 注意要是链表长度为零, 那么就不用 % 了, 直接返回就可以了
        if (n == 0) {
            return newHead.next;
        }

        // 要头插的末尾节点
        ListNode last = cur;

        // 要是超过链表的长度的就变为原样了
        k %= n;

        // 这里我们还要判断一下 需要头插的节点数量是否为 0 , 要是为零,
        // 那么也是直接返回就可以了
        // 要是没有返回的话, 后面我们求的 first 节点就会 为 null, 那么
        // 我们的newHead.next 就会指向 null
        if (k == 0) {
            return newHead.next;
        }

        // 这里我们要遍历到需要头插的第一个节点的前节点
        // 这个是要遍历的数
        int m = n - k;

        // 重置打工节点
        cur = newHead;
        while (m != 0) {
            cur = cur.next;
            m--;
        }

        // 要头插的头结点
        ListNode first = cur.next;

        // 将后面需要头插的节点一起头插
        cur.next = null;
        last.next = newHead.next;
        newHead.next = first;

        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}